
class GraphError(Exception):
    pass

class Edge(object):

    def __init__(self, graph, source, target):
        self._graph = graph
        self._source = source
        self._target = target
        self._order = 0


    # Setting graph property
    def getgraph(self):
        return self._graph

    def setgraph(self, graph):
        pass #TODO

    graph = property(getgraph, setgraph)


    # Setting source property
    def getsource(self):
        return self._source

    def setsource(self, source):
        pass #TODO

    source = property(getsource, setsource)


    # Setting tagret property
    def gettarget(self):
        return self._target

    def settarget(self, target):
        pass #TODO

    target = property(gettarget, settarget)


    # Setting order property
    def getorder(self):
        return self._order

    order = property(getorder)

    # Setting id property
    def getid(self):
        return (self._source._id, self._target._id)

    id = property(getid)


    def __repr__(self):
        return repr(self.getid())

    def __getitem__(self, key):
        G = self._graph
        if G.isvertex(key):
            v = G[key]
            if self._source == v: return self._target
            if self._target == v: return self._source
            raise GraphError("Edge %s hasn't end-vertex %s"%(self, v))
        elif G.isedge(key):
            e = G[key]
            if self._source == e._source: return self._source
            if self._source == e._target: return self._source
            if self._target == e._source: return self._target
            if self._target == e._target: return self._target
            raise GraphError("Edges %s and %s haven't cross-vertex"%(self, e))
        else:
            raise GraphError("Element %s doesn't belong to graph"%str(key))

class Vertex(object):

    def __init__(self, graph, id):
        self._graph = graph
        self._id = id
        self._neighbors = {} # maps neighbor vertex to edge
        self._order = 0

    # Setting graph property
    def getgraph(self):
        return self._graph

    def setgraph(self, graph):
        pass #TODO

    graph = property(getgraph, setgraph)

    # Setting degree property
    def getdegree(self):
        return len(self._neighbors)

    degree = property(getdegree)

    # Setting neighbors property
    def getneighbors(self):
        return sorted(self._neighbors.keys(), key=Vertex.getorder)

    neighbors = property(getneighbors)

    # Setting order property
    def getorder(self):
        return self._order

    order = property(getorder)

    # Setting id property
    def getid(self):
        return self._id

    id = property(getid)


    def __repr__(self):
        return repr(self._id)

    def __getitem__(self, key):
        G = self._graph
        if G.isvertex(key):
            v = G[key]
            try:
                return self._neighbors[v] # v[u] returns edge (v,u)
            except KeyError:
                raise GraphError("Edge (%s, %s) doesn't exist"%(self, v))
        elif G.isedge(key):
            e = G[key]
            return e[self]              # v[e] returns opposite vertex of edge e relative to v
        else:
            raise GraphError("Element %s doesn't belong to graph"%str(key))

    def __setitem__(self, key, item):
        #G = self.graph
        #if G.isset(key):
        #    if G.isvertex(key):
        pass

    def __delitem__(self, key):
        G = self._graph
        if G.isvertex(key):
            G._deledge(self[key])
        elif G.isedge(key):
            raise GraphError("Operation del v[e] doesn't supported")
        else:
            raise GraphError("Element %s doesn't belong to graph"%str(key))


class Graph(object):

    def __init__(self, init=None):

        if init is None:
            self._vertices = {} # maps Vertex to list of neighbors
            self._edges = []# list of edges in order of time creating
            self._ids = {} #maps id to Vertex
            self._orders = [] #list of vertices in order of time creating
        else:
            pass #TODO parse given dictionary and construct graph

    def __repr__(self):
        return '{'+", ".join([(repr(v._id)+': '+repr([u._id for u in v.getneighbors()])) for v in self._orders])+'}'


    def vorder(self, value):
        if isinstance(value, int):
            try:
                return self._orders[value]
            except IndexError:
                raise GraphError("Vertex with order %i doesn't exist"%value)
        else:
            raise GraphError("The value must be positive integer")

    def eorder(self, value):
        if isinstance(value, int):
            try:
                return self._edges[value]
            except IndexError:
                raise GraphError("Edge with order %i doesn't exist"%value)
        else:
            raise GraphError("The value must be positive integer")


    def isvertex(self, obj):
        if isinstance(obj, Vertex):
            return obj in self._vertices
        else:
            return obj in self._ids

    def isedge(self, obj1, obj2=None):
        if obj2 is None:
            if isinstance(obj1, Edge):
                return obj1 in self._edges
            elif isinstance(obj1, tuple):
                if len(obj1) == 2:
                    s, t = obj1
                    return self.isedge(s, t)
            return False
        elif self.isvertex(obj1) and self.isvertex(obj2):
            obj1 = self[obj1]
            obj2 = self[obj2]
            return obj2 in self._vertices[obj1]
        return False

    def __getitem__(self, key):
        if isinstance(key, Vertex):
            if key in self._vertices:
                return key
        elif isinstance(key, Edge):
            if key in self._edges:
                return key
        elif isinstance(key, tuple):
            if len(key) == 2:
                u, v = key
                return self[u][v]
        else:
            try:
                return self._ids[key]
            except KeyError:
                pass
        raise GraphError("Element %s doesn't belong to graph"%str(key))

    def __setitem__(self, key, item):
        pass

    def __delitem__(self, key):

        if self.isvertex(key):
            self._delvertex(self[key])
        elif self.isedge(key):
            self._deledge(self[key])
        else:
            raise GraphError("Element %s doesn't belong to graph"%str(key))

    def _delvertex(self, vertex):
        """
        Private function, deletes vertex
        and all incident edges.
        Does not check parameter.
        """

        # delete all edges between v and its neighbors
        for e in vertex._neighbors.values():
            self._deledge(e)

        del self._vertices[vertex]
        del self._ids[vertex._id]

        order = vertex._order
        del self._orders[order]
        for v in self._orders[order:]:
            v._order -= 1

        del vertex

    def _deledge(self, edge):
        """
        Private function for deleting edge,
        its refactored in separate function
        for simple calling when deletes vertex
        whith incident edges.
        Does not check parameter.
        """

        source = edge._source
        target = edge._target
        del source._neighbors[target]
        del target._neighbors[source]
        self._vertices[source].remove(target)
        self._vertices[target].remove(source)

        order = edge._order
        del self._edges[order]
        for e in self._edges[order:]:
            e._order -= 1

        del edge


    def __contains__(self, item):
        if self.isvertex(item):
            return True
        else:
            return self.isedge(item)


    def keys(self):
        return self._vertices.keys()

    def vertex(self, id):

        if isinstance(id, Vertex):
            raise GraphError("Vertex can't have id with type 'Vertex'")
        if id in self._ids:
            raise GraphError("Duplicate vertex %s"%str(id))
        else:
            v = Vertex(self, id)
            self._vertices[v] = []
            self._ids[id] = v
            v._order = len(self._orders)
            self._orders.append(v)
            return v

    def edge(self, u, v):

        if not self.isvertex(u):
            raise GraphError("Graph contains no vertex %s"%str(u))

        if not self.isvertex(v):
            raise GraphError("Graph contains no vertex %s"%str(v))

        u = self[u]
        v = self[v]

        if u == v:
            raise GraphError("Graph can't contain a loop")

        if self.isedge(u, v):
            e = self[u][v]
            raise GraphError("Duplicate edge %s"%e)

        e = Edge(self, u, v)

        e._order = len(self._edges)
        self._edges.append(e)

        self._vertices[u].append(v)
        self._vertices[v].append(u)

        u._neighbors[v] = e
        v._neighbors[u] = e

        return e

    def delete(self, item):
        del self[item]

    def __len__(self):
        return len(self._vertices)

    def N(self, vertex):
        v = self[vertex]
        return v.getneighbors()

    def getV(self):
        return list(self._orders)

    V = property(getV)

    def getE(self):
        return list(self._edges)

    E = property(getE)

